package cn.edu.besti.cs1723.DZX2304;

import week7.jsjf.LinkedBinarySearchTree;
import week8.jsjf.LinkedHeap;

import java.util.Iterator;

/**
 *
 */
public class Sorting {
    public static <T extends Comparable<T>> T[] selectionSort(T[] data)
    {
        int min;
        T temp;

        for (int index = 0; index < data.length-1; index++)
        {
            min = index;
            for (int scan = index+1; scan < data.length; scan++)
                if (data[scan].compareTo(data[min])<0)
                    min = scan;

            swap(data, min, index);
        }
        return data;
        }





        // 插入排序
        public static <T extends Comparable<? super T>> void insertionSort(T[] data)
        {
            for (int index = 1; index < data.length; index++)
            {
                T key = data[index];
                int position = index;

                // 元素向后移动一位
                while (position > 0 && data[position-1].compareTo(key) > 0)
                {
                    data[position] = data[position-1];
                    position--;
                }

                data[position] = key;
            }
        }



        // 快速排序
        public static <T extends Comparable<T>> void quickSort(T[] data)
        {
            quickSort(data, 0, data.length - 1);
        }

        private static <T extends Comparable<T>> void quickSort(T[] data, int min, int max)
        {
            if (min < max)
            {
                // create partitions
                int indexofpartition = partition(data, min, max);

                // sort the left partition (lower values)
                quickSort(data, min, indexofpartition - 1);

                // sort the right partition (higher values)
                quickSort(data, indexofpartition + 1, max);
            }
        }

        private static <T extends Comparable<T>> int partition(T[] data, int min, int max)
        {
            T partitionelement;
            int left, right;
            int middle = (min + max) / 2;

            //使用中间数据值作为分区元素
            partitionelement = data[middle];
            // 暂时把它移开
            swap(data, middle, min);

            left = min;
            right = max;

            while (left < right)
            {
                // 搜索一个元素，它是>分区元素
                while (left < right && data[left].compareTo(partitionelement) <= 0)
                    left++;

                // 搜索一个元素，它是<分区元素
                while (data[right].compareTo(partitionelement) > 0)
                    right--;

                // 交换元素
                if (left < right)
                    swap(data, left, right);
            }

            // 将分区元素移动到适当的位置
            swap(data, min, right);

            return right;
        }




        // 希尔排序
        public static <T extends Comparable<T>>void shellSort(T[] data)
        {
            for(int gap=data.length/2;gap>0;gap=gap/2)
            {
                for(int i=gap;i<data.length;i++)
                {
                    int j = i;
                    while(j-gap>=0 && data[j].compareTo(data[j-gap])<0)
                    {
                        swap(data,j,j-gap);
                        j-=gap;
                    }
                }
            }
        }

        private static <T extends Comparable<? super T>> void swap(T[] data, int index1, int index2)
        {
            T temp = data[index1];
            data[index1] = data[index2];
            data[index2] = temp;
        }

        // 堆排序
        public static <T extends Comparable<T>>void heapSort(T[] data)
        {
            LinkedHeap<T> linkedHeap = new LinkedHeap<>();
            for (int i=0;i<data.length;i++)
                linkedHeap.addElement(data[i]);
            for (int i=0;i<data.length;i++)
                data[i] = linkedHeap.removeMin();
        }

        // 二叉查找树排序
        public static <T extends Comparable<T>>void binarySearchTreeSort(T[] data)
        {
            LinkedBinarySearchTree<T> linkedBinarySearchTree = new LinkedBinarySearchTree<>();
            for (int i=0;i<data.length;i++)
                linkedBinarySearchTree.addElement(data[i]);

            Iterator iterator = linkedBinarySearchTree.iteratorInOrder();
            int index = 0;
            while (iterator.hasNext())
            {
                data[index] = (T) iterator.next();
                index++;
            }
        }
    }


